package top.lywivan.tree;

import javax.swing.tree.TreeNode;

/**
 * @desc
 * @author:ivan.liu
 */
public class BinarySearchTree {

    //根节点
    private TreeNode root;

    public boolean add(int val){
        if(root==null){
            root=new TreeNode(val);
            return true;
        }
        TreeNode curr=root;
        while(curr!=null){
            if(val>curr.val){
                if(curr.right==null){
                    curr.right=new TreeNode(val);
                    return true;
                }
                curr=curr.right;
            }else if (val<curr.val){
                if(curr.left==null){
                    curr.left=new TreeNode(val);
                    return true;
                }
                curr=curr.left;
            }else {
                return false;
            }
        }
        return false;
    }

    public TreeNode get(int val){
        TreeNode curr=root;
        while (curr!=null){
            if(val>curr.val){
                curr=curr.right;
            }else if (val<curr.val){
                curr=curr.left;
            }else {
                return curr;
            }
        }
        return null;
    }

    public void remove(int val){
        if(root==null){
            return;
        }
        TreeNode del=root;
        TreeNode del_p=null;
        while (del!=null){
            if(del.val<val){
                del_p=del;
                del=del.right;
            }else if(del.val>val){
                del_p=del;
                del=del.left;
            }else {
                break;
            }
        }
        if(del==null){
            return;
        }
        //已经拿到了需要被删除的节点
        //处理两个子节点的情况
        if(del.left!=null&&del.right!=null){
            TreeNode min=del.right;
            TreeNode min_p=null;
            while (min.left!=null){
                min_p=min;
                min=min.left;
            }
            //找到了右子树的最小值
            del.val=min.val;
            del=min;
            del_p=min_p;
        }
        //处理一个节点的情况
        TreeNode del_child=null;
        if(del.left!=null){
            del_child=del.left;
        }else if(del.right!=null){
            del_child=del.right;
        }
        //处理无子节点的情况
        if(del_p.right==del){
            del_p.right=del_child;
        }else if (del_p.left==del){
            del_p.left=del_child;
        }
        del.left=null;
        del.right=null;
    }

    //从BST中查询最大值
    public TreeNode getMax(){
        if(root==null){
            return null;
        }
        TreeNode max=root;
        if (max.right!=null){
            max=max.right;
        }
        return max;
    }

    //从BST中查询最小值
    public TreeNode getMin(){
        if(root==null){
            return null;
        }
        TreeNode min=root;
        if (min.left!=null){
            min=min.left;
        }
        return min;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        printRecur(sb,root);
        return sb.toString();
    }

    private void printRecur(StringBuilder sb,TreeNode root) {
        if(root==null){
            return;
        }
        printRecur(sb,root.left);
        sb.append(root.val).append("->");
        printRecur(sb,root.right);
    }

    private class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
